package leetcodesolution;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 涛
 * Date: 2023-10-06
 * Time: 17:35
 */
//力扣题：判断一个树是不是和另一个树的子树相等
class TreeNode1 {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode1() {}
    TreeNode1(int val) { this.val = val; }
    TreeNode1(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
//复杂度：O(m * n)
public class Solution3 {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null || subRoot == null) {
            return false;
        }
        //判断是不是和根节点的相同
        if(isSameTree(root, subRoot)) {
            return true;
        }
        //不相等开始下面的判断
        //判断是不是root的左子树
        if(isSubtree(root.left, subRoot)) {
            return true;
        }
        //判断是不是root的右子树
        if(isSubtree(root.right, subRoot)) {
            return true;
        }
        //返回
        return false;
    }


    public boolean isSameTree(TreeNode p, TreeNode q) {
        //一个空，一个不为空，不相同
        if((p == null && q != null) || (p != null && q == null)) {
            return false;
        }
        //走完上面的代码后，要么两个树都不为空，要么两个树都为空
        //判断两个节点是不是空,都为空就是相同的
        if(p == null && q == null) {
            return true;
        }

        //剩下的就是都不为空了，判断其中的值
        if(p.val != q.val) {
            //两个树的值不相同
            return false;
        }
        //两个树都不为空，且两个树的值都相同，那么就要开始比较他们的左右子树是否相同了
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}
